1. Field of the Invention
This invention relates to the field of signal processing for identification of spectral content and, more particularly, to the identification of received electromagnetic signals by development of the corresponding discrete Fourier transform.
2. Description of the Related Art
The discrete Fourier transform (DFT) is particularly useful in facilitating signal analysis, such as power spectrum analysis and the like. An algorithm for the computation of Fourier coefficients which requires much less computational effort than had been previously required was reported by Cooley and Tukey in 1965. This method is now generally referred to as the "fast Fourier transform" (FFT) and is effective for efficiently computing the discrete Fourier transform of a time series of discrete data samples.
The discrete Fourier transform (DFT) is a transform in its own right, such as the Fourier integral transform or the Fourier series transform. It is a powerful reversible mapping operation for time series. It has mathematical properties that are entirely analogous to those of the Fourier integral transform. In particular, it defines a spectrum of a time series; multiplication of the transforms of two time series corresponds to convolving the time series.
For digital techniques to be used for analyzing a continuous waveform, it is necessary that the data be sampled (usually at equally spaced intervals of time) in order to produce a time series of discrete samples which can be fed to a digital computer for processing. Such a time series adequately represents the continuous waveform so long as the waveform is frequency band-limited and the samples are taken at a rate that is at least twice the highest frequency of interest in the waveform, thus satisfying the Nyquist criterion. The DFT of such a time series is closely related to the Fourier transform of the continuous waveform from which samples have been taken to form the time series, thus making the DFT particularly useful for power spectrum analysis and frequency identification. Since the announcement of the fast Fourier transform, the FFT has come into wide use as a powerful tool for computing the DFT of a time series. In comparison with the number of operations (and corresponding computer time involved) required for the calculation of the DFT coefficients with straightforward procedures, the number of operations required in using FFT techniques is vastly reduced, particularly where the time series consists of a relatively large number of samples. For example, it has been reported that for a time series represented by 8192 samples, the computations using the FFT method require about five seconds for the evaluation of all 8192 DFT coefficients on an IBM 7094 computer, whereas conventional procedures take on the order of half an hour.
Since the announcement of the fast Fourier transform algorithm, considerable effort has gone into developing and refining the techniques involved in specific applications, and the prior art contains many references relating to use of the FFT in processing of data. For example, a tutorial discussion of the FFT and its relationship to the DFT is to be found in an article by Cochran et al entitled "What Is The Fast Fourier Transform?," PROCEEDINGS OF THE IEEE, Vol. 55, No. 10, October, 1967, pp. 1664ff. Use of a special purpose computer utilizing FFT techniques is detailed in a publication by Klahn et al, entitled "The Time-Saver: FFT Hardware", ELECTRONICS, June 24, 1968, pp. 92-97.
While the FFT presents a considerable improvement over previously known signal processing techniques, it is not without its disadvantages, particularly when considered in a particular utilization to which the present invention is directed--namely, the analysis of a received signal for immediate identification of the spectral content. For example, the FFT requires using all frequencies; it cannot selectively look at a single frequency or band of frequencies within the received signal bandwidth. Also, the FFT develops an inherent transport delay because the FFT processor cannot begin operation until all samples of the time series have been acquired. By contrast, arrangements in accordance with the present invention have no transport delay and the output of the transform can be provided within one sample period after the last sample is received.